#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1), count(n, 1);
        for (int i = 1; i < n; i++)
            for (int j = i - 1; j >= 0; j--)
                if (nums[i] > nums[j])
                    if (1 + dp[j] == dp[i]) count[i] += count[j];
                    else if (1 + dp[j] > dp[i])
                        dp[i] = 1 + dp[j], count[i] = count[j];

        int max_len = 1, ret = 0;
        for (int i = 0; i < n; i++)
            if (max_len == dp[i]) ret += count[i];
            else if (max_len < dp[i])
                max_len = dp[i], ret = count[i];

        return ret;
    }
};